//
//  86_分隔链表.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/8.
/**
 https://leetcode.cn/problems/partition-list/description/
 输入：head = [1,4,3,2,5,2], x = 3
 输出：[1,2,2,4,3,5]
 
 示例 2：
 输入：head = [2,1], x = 2
 输出：[1,2]
 */

import UIKit

class FenGeLink: NSObject {
    func QA() {
        var link =  LinkedList<Int>()
        let head = link.creatList(array: [1,2,6,3,4,5,6])
        let newHead = partition(head, 5)
        LinkedList.printList(newHead)
    }
    
    func partition(_ head: ListNode<Int>?, _ x: Int) -> ListNode<Int>? {
        if head == nil {
            return nil
        }
        let minHead = ListNode(0)
        var minCurrent = minHead
        let maxHead = ListNode(0)
        var maxCurrent = maxHead
        var head = head
        while let temp = head {
            if temp.val < x {
                minCurrent.next = temp
                minCurrent = temp
            } else {
                maxCurrent.next = temp
                maxCurrent = temp
            }
            head = temp.next
        }
        maxCurrent.next = nil
        minCurrent.next = maxHead.next
        return minHead.next
    }
}
